package LeetCodeHot100;

import java.util.ArrayList;
import java.util.List;

/**
 * 46. 全排列
 *  给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 * 思路： 使用递归实现 , 可以使用一个visit[] 数组进行判断 ， 全排列，全排列，就是循环遍历的过程，只要通过一个中间变量，将循环遍历中已经访问的节点跳过，就可以收集到所有的全排列信息。
 *       主要是使用回溯实现， 循环遍历，但是可以通过使用一个 visit【】 数组进行全排列
 */
public class LeetCode46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        int[] visit = new int[nums.length];
        rescur(res,nums,tmp,visit);
        return res;
    }

    /**
     * 回溯全排列
     * @param res 结果集
     * @param nums  需要排列的数组
     * @param tmp  临时数组，用于排列
     * @param visit  检视数组，判断是否已经遍历
     */
    private void rescur(List<List<Integer>> res, int[] nums, List<Integer> tmp, int[] visit){
        if(tmp.size() == nums.length){
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length ; i++) {
            if(visit[i] == 1){
                continue;
            }
            visit[i] = 1;
            tmp.add(nums[i]);
            rescur(res,nums,tmp,visit);
            visit[i] = 0;
            tmp.remove(tmp.size()-1);
        }
    }
}
